package com.lft.graph05.shortest_path_graph03_spfa;

import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 无向图的实现——邻接矩阵
 */
public class GraphAdjacencyMatrix<E> implements GraphInterface<E> {
	/**
	 * 存储图的顶点的一维数组
	 */
	private E[] vertexs;
	
	/**
	 * 存储图的边的二维数组
	 */
	private int[][] edges;
	
	// /**
	//  * 存储各个顶点最短路径的信息
	//  */
	// private Distance[] dis;
	/**
	 * 记录各个顶点最短路径的信息
	 */
	private int[][] dis;
	
	/**
	 * 记录各个最短路径的信息
	 */
	private int[][] path;
	
	/**
	 * 顶点的实际数量
	 */
	private int numOfVertexs;
	
	/**
	 * 顶点的最大数量
	 */
	private int maxNumOfVertexs;
	
	/**
	 * 判断顶点是否被反问过。 true：访问过；false：未访问过。
	 */
	private boolean[] visited;
	
	/**
	 * 构造器，初始化顶点数组和边数组。
	 * @param maxNumOfVertexs
	 * @param type
	 */
	public GraphAdjacencyMatrix(int maxNumOfVertexs, Class<E> type) {
		this.maxNumOfVertexs = maxNumOfVertexs;
		edges = new int[maxNumOfVertexs][maxNumOfVertexs];
		vertexs = (E[]) Array.newInstance(type, maxNumOfVertexs);
	}
	
	/**
	 * 获取顶点的个数。
	 * @return
	 */
	@Override
	public int getNumOfVertex() {
		return numOfVertexs;
	}
	
	/**
	 * 插入顶点
	 * @param v
	 * @return
	 */
	@Override
	public boolean insertVertex(E v) {
		if (numOfVertexs >= maxNumOfVertexs) {
			return false;
		}
		vertexs[numOfVertexs++] = v;
		return true;
	}
	
	/**
	 * 删除顶点
	 * @param v
	 * @return
	 */
	@Override
	public boolean deleteVertex(E v) {
		// 遍历每个顶点
		for (int i = 0; i < numOfVertexs; i++) {
			// 当前顶点跟要删除的顶点相等。
			if (vertexs[i].equals(v)) {
				// 遍历将当前顶点用后面的顶点替换删除。
				for (int j = i; j < numOfVertexs - 1; j++) {
					// 遍历顶点数组，将后面的往前移动，替换掉要删除的顶点。
					vertexs[j] = vertexs[j + 1];
				}
				// 将数组末尾置空。
				vertexs[numOfVertexs - 1] = null;
				// 遍历列，修改边
				for (int col = i; col < numOfVertexs - 1; col++) {
					for (int row = 0; row < numOfVertexs; row++) {
						edges[col][row] = edges[col + 1][row];
					}
				}
				// 遍历行，修改边
				for (int row = i; row < numOfVertexs - 1; row++) {
					for (int col = 0; col < numOfVertexs; col++) {
						edges[col][row] = edges[col][row + 1];
					}
				}
				// 顶点数量减1
				numOfVertexs--;
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 定位顶点的位置
	 * @param v 要查找的顶点。
	 * @return -1 未找到。其他值就是顶点的索引。
	 */
	@Override
	public int indexOfVertex(E v) {
		for (int i = 0; i < numOfVertexs; i++) {
			if (vertexs[i].equals(v)) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 查找指定位置的顶点的值
	 * @param vertexIndex
	 * @return
	 */
	@Override
	public E valueOfVertex(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			return null;
		}
		return vertexs[vertexIndex];
	}
	
	/**
	 * 检查边的索引和权重值是否合法
	 * @param vertexIndex1
	 * @param vertexIndex2
	 * @param weight
	 * @return
	 */
	@Override
	public boolean checkEdgeValue(int v1, int v2, int weight) {
		if (v1 < 0 || v1 > numOfVertexs || v2 < 0 || v2 > numOfVertexs || weight < 0) {
			return false;
		}
		return true;
	}
	
	/**
	 * 插入边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @param weight       权重 1表示连接。0表示不通。
	 * @return 插入成功返回 true;
	 */
	@Override
	public boolean insertEdge(int vertexIndex1, int vertexIndex2, int weight) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		edges[vertexIndex1][vertexIndex2] = weight;
		// 无向图添加下行。
		edges[vertexIndex2][vertexIndex1] = weight;
		return true;
	}
	
	/**
	 * 删除边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return 删除成功 返回true.
	 */
	@Override
	public boolean deleteEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		edges[vertexIndex1][vertexIndex2] = 0;
		// 无向图添加下行。
		edges[vertexIndex2][vertexIndex1] = 0;
		return true;
	}
	
	/**
	 * 查找顶点1与顶点2边的权值
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return 权值
	 */
	@Override
	public int getEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		return edges[vertexIndex1][vertexIndex2];
	}
	
	/**
	 * 邻接矩阵-深度优先搜索遍历——基于栈实现
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String depthFirstSearchByStack(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex > numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 初始化 访问标记数组
		visited = new boolean[numOfVertexs];
		// 创建 StringBuilder 对象，用于遍历输出打印。
		StringBuilder sb = new StringBuilder();
		// 创建一个栈，入栈出栈的是索引。
		Stack<Integer> stack = new Stack<>();
		// 先将当前顶点的索引压入栈中。
		stack.push(vertexIndex);
		// 将当前索引的访问标记设置为 true
		visited[vertexIndex] = true;
		// 只要栈不为空，循环遍历
		while (!stack.isEmpty()) {
			// 弹出栈顶索引。赋值给 vertexIndex
			vertexIndex = stack.pop();
			// 将 vertexIndex 索引下的顶点的值拼接到 sb 中。
			sb.append(vertexs[vertexIndex] + ",");
			// 从最后一个顶点开始 循环遍历
			for (int i = numOfVertexs - 1; i >= 0; i--) {
				// 如果 vertexIndex 顶点 和 i 顶点 连通。且权值是一个正常整数。且顶点访问标记是未访问。
				if (edges[vertexIndex][i] != 0 && edges[vertexIndex][i] != Integer.MAX_VALUE && !visited[i]) {
					// 将 i 索引压入栈中。
					stack.push(i);
					// 将 i 索引的顶点标记为 已访问。
					visited[i] = true;
				}
			}
		}
		// sb 长度大于0，将 sb 从头到尾返回，否则返回 null
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接矩阵-深度优先搜索遍历——基于递归
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String depthFirstSearchByRecursion(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		visited = new boolean[numOfVertexs];
		StringBuilder sb = new StringBuilder();
		depthFirstSearchByRecursion(vertexIndex, sb);
		// 如果图是非连通图，那么我们这里还需要对每个顶点遍历一次，保证全部顶点都被访问到了。
		for (int i = 0; i < numOfVertexs; i++) {
			// 如果有顶点没有被访问过。调用递归方法访问一下。
			if (!visited[i]) {
				depthFirstSearchByRecursion(i, sb);
			}
		}
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接矩阵-用于递归DFS遍历
	 * @param vertexIndex
	 * @param sb
	 * @return
	 */
	private StringBuilder depthFirstSearchByRecursion(int vertexIndex, StringBuilder sb) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		sb.append(vertexs[vertexIndex] + ",");
		visited[vertexIndex] = true;
		// 找到下一个未被访问的顶点
		for (int i = 0; i < numOfVertexs; i++) {
			// 如果两个顶点不存在边。
			if (edges[vertexIndex][i] == 0 || edges[vertexIndex][i] == Integer.MAX_VALUE) {
				continue;
			}
			// 如果没有被访问，访问该节点
			else if (!visited[i]) {
				depthFirstSearchByRecursion(i, sb);
			}
		}
		return sb;
	}
	
	/**
	 * 邻接矩阵-广度优先搜索遍历——基于队列实现
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public String breadFirstSearchByStack(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 初始化访问标志
		visited = new boolean[numOfVertexs];
		StringBuilder sb = new StringBuilder();
		// 创建一个队列。
		Queue<Integer> queue = new LinkedList<>();
		// 调用方法进行广度优先遍历
		breadFirstSearchByStack(vertexIndex, sb, queue);
		// 返回遍历到的顶点数据
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}
	
	/**
	 * 邻接矩阵-真实的广度优先搜索遍历方法
	 * @param vertexIndex
	 * @param sb
	 * @param queue
	 * @return
	 */
	private StringBuilder breadFirstSearchByStack(int vertexIndex, StringBuilder sb, Queue<Integer> queue) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 添加当前索引到队列
		queue.offer(vertexIndex);
		// 设置当前顶点访问标志为true
		visited[vertexIndex] = true;
		// 队列不为空，一直遍历。
		while (!queue.isEmpty()) {
			// 出队列的值赋值给 vertexIndex
			vertexIndex = queue.poll();
			// 将当前顶点的数据添加到 sb 中。
			sb.append(vertexs[vertexIndex] + ",");
			// 遍历
			for (int i = 0; i < numOfVertexs; i++) {
				// 两个顶点存在边，并且未被访问。
				if (edges[vertexIndex][i] != 0 && edges[vertexIndex][i] != Integer.MAX_VALUE && !visited[i]) {
					queue.offer(i);
					visited[i] = true;
				}
			}
		}
		// 再遍历一次。以防有顶点没有边的情况
		for (int i = 0; i < numOfVertexs; i++) {
			if (visited[i]) {
				continue;
			} else {
				breadFirstSearchByStack(i, sb, queue);
			}
		}
		return sb;
	}
	
	/**
	 * 邻接矩阵-最短路径算法1——迪杰斯特拉算法
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public int[] dijkstra(int vertexIndex) {
		// if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
		// 	throw new ArrayIndexOutOfBoundsException();
		// }
		// // 创建 Distance 数组
		// dis = new Distance[numOfVertexs];
		// // 初始化
		// for (int i = 0; i < numOfVertexs; i++) {
		// 	dis[i] = new Distance();
		// }
		// // 首先初始化我们的dis数组
		// for (int i = 0; i < numOfVertexs; i++) {
		// 	// 设置当前路径
		// 	dis[i].path = "V" + (vertexIndex + 1) + " --> V" + (i + 1);
		// 	dis[i].value = edges[vertexIndex][i];
		// }
		// // 循环遍历边的权重，如果两条边不能连通，就将边的权重设置为最大值。
		// for (int i = 0; i < numOfVertexs; i++) {
		// 	for (int j = i; j < numOfVertexs; j++) {
		// 		if (edges[i][j] == 0) {
		// 			edges[i][j] = Integer.MAX_VALUE;
		// 			edges[j][i] = Integer.MAX_VALUE;
		// 		}
		// 	}
		// }
		//
		// // 设置源点到源点的路径为0
		// dis[vertexIndex].value = 0;
		// // 设置源点已经访问过了。
		// dis[vertexIndex].visit = true;
		//
		// int count = 1;
		// // 计算其他顶点的最短路径 剩余 numOfVertexs-1个顶点
		// // 用于遍历每个顶点
		// while (count != numOfVertexs) {
		// 	// index 用于保存当前 dis 数组中最小的那个下标。
		// 	int index = -1;
		// 	int min = Integer.MAX_VALUE;
		// 	// 遍历每个顶点
		// 	for (int i = 0; i < numOfVertexs; i++) {
		// 		// 如果顶点 i 没有查找过最短路径。并且 源点到顶点 i 的值小于最小路径值。
		// 		if (!dis[i].visit && dis[i].value < min) {
		// 			// 把最小路径值改为源点到顶点 i 的值
		// 			min = dis[i].value;
		// 			// 把最小值的索引 index 指向 i
		// 			index = i;
		// 		}
		// 	}
		// 	if (index != -1) {
		// 		// 把 index 对应的顶点加入到已经找到的最短路径的集合中。
		// 		dis[index].visit = true;
		// 	}
		// 	for (int i = 0; i < numOfVertexs; i++) {
		// 		// 顶点 i 未查找过最短路径。并且顶点 index 到 顶点 i 的路径权重不是最大值。
		// 		// 源点到 index 顶点的值 + index 顶点 到 顶点 i 的值 比 源点到 顶点i的值小。
		// 		if (!dis[i].visit && edges[index][i] != Integer.MAX_VALUE && (dis[index].value + edges[index][i]) < dis[i].value) {
		// 			// 那就修改源点到顶点 i 的值 和路径
		// 			dis[i].value = dis[index].value + edges[index][i];
		// 			// 将源点到 顶点 i 的路径修改 为 源点到 顶点index 路径 再 到 顶点 i 的路径
		// 			dis[i].path = dis[index].path + " --> V" + (i + 1);
		// 		}
		// 	}
		// 	count++;
		// }
		// int[] shortestValues = new int[numOfVertexs];
		// for (int i = 0; i < dis.length; i++) {
		// 	shortestValues[i] = dis[i].value;
		// }
		// return shortestValues;
		return new int[0];
	}
	// /**
	//  * 查询源点 至 某一顶点的最短路径值。
	//  * @param vertexIndex1
	//  * @param vertexIndex2
	//  * @return
	//  */
	// public int dijkstraSearch(int vertexIndex1, int vertexIndex2) {
	// 	return dijkstra(vertexIndex1)[vertexIndex2];
	// }
	//
	// /**
	//  * 查询源点 至 某一顶点的最短路径
	//  * @param vertexIndex1
	//  * @param vertexIndex2
	//  * @return
	//  */
	// public String dijkstraPathSearch(int vertexIndex1, int vertexIndex2) {
	// 	dijkstra(vertexIndex1);
	// 	return dis[vertexIndex2].path;
	// }
	
	/**
	 * 邻接矩阵-最短路径算法2——弗洛伊德算法
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public int[] floyd(int vertexIndex) {
		int row = 0;
		int col = 0;
		dis = new int[numOfVertexs][numOfVertexs];
		path = new int[numOfVertexs][numOfVertexs];
		
		// 初始化两个矩阵
		for (row = 0; row < numOfVertexs; row++) {
			for (col = 0; col < numOfVertexs; col++) {
				// 把矩阵 D 初始化为邻接矩阵的值
				dis[row][col] = edges[row][col] == 0 ? Integer.MAX_VALUE : edges[row][col];
				// 把矩阵 P 初始化各个边的终点顶点的下标。
				path[row][col] = col;
			}
		}
		// 三重循环，用于计算每个点对的最短路径。
		int index = 0;
		int min = 0;
		// 最外围循环用于找到最小值（中间值） 的索引 index 和值 min
		for (index = 0; index < numOfVertexs; index++) {
			// 遍历行
			for (row = 0; row < numOfVertexs; row++) {
				// 遍历列
				for (col = 0; col < numOfVertexs; col++) {
					// row 和 index 顶点不通 或者 index 和 col 顶点不通
					min = (dis[row][index] == Integer.MAX_VALUE || dis[index][col] == Integer.MAX_VALUE)
							?
							// 不通，min 为 最大值。
							Integer.MAX_VALUE
							// 通的，min 就是顶点 row 到顶点 index 的值 + 顶点 index 到顶点 col 值。
							: (dis[row][index] + dis[index][col]);
					// 判断 顶点 row 到 顶点 col 的值 是否大于 min
					if (dis[row][col] > min) {
						// 更新 D 矩阵
						dis[row][col] = min;
						// 更新 P 矩阵
						path[row][col] = path[row][index];
					}
				}
			}
		}
		return dis[vertexIndex];
	}
	
	/**
	 * 邻接矩阵-最短路径算法3——SPFA 算法
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	@Override
	public boolean spfa(int vertexIndex) {
		return false;
	}
	
	/**
	 * 打印邻接矩阵
	 */
	@Override
	public void displayGraph() {
		System.out.println("图的邻接矩阵为：");
		// 打印行标签
		int count_row = 0;
		// 打印列标签
		int count_col = 0;
		while (count_row != numOfVertexs) {
			count_col = 0;
			while (count_col != numOfVertexs) {
				if (edges[count_row][count_col] == Integer.MAX_VALUE) {
					System.out.print("∞\t");
				} else {
					System.out.print(edges[count_row][count_col] + "\t");
				}
				count_col++;
			}
			System.out.println();
			count_row++;
		}
	}
	
	// /**
	//  * Dijkstra最短路径的打印
	//  */
	// @Override
	// public void displayShortestPath(int vertexIndex) {
	// 	dijkstra(vertexIndex);
	// 	String str;
	// 	str = "V" + (vertexIndex + 1);
	// 	System.out.println("以 " + str + " 为起点的力的最短路径为：");
	// 	for (int i = 0; i < numOfVertexs; i++) {
	// 		if (dis[i].value != Integer.MAX_VALUE) {
	// 			System.out.println(dis[i].path + " = " + dis[i].value);
	// 		} else {
	// 			System.out.println(dis[i].path + " 是无最短路径的。");
	// 		}
	// 	}
	// }
	
	/**
	 * Dijkstra最短路径的打印
	 */
	@Override
	public void displayShortestPath(int vertexIndex) {
		System.out.println("各个顶点对的最短路径：");
		int row = 0;
		int col = 0;
		int index = 0;
		for (row = 0; row < numOfVertexs; row++) {
			for (col = row + 1; col < numOfVertexs; col++) {
				System.out.print("V" + (row + 1) + " --> V" + (col + 1) + "\tWeight:" + dis[row][col] + "\tPath: V" + (row + 1));
				index = path[row][col];
				while (index != col) {
					System.out.print(" --> V" + (index + 1));
					index = path[index][col];
				}
				System.out.println(" --> V" + (col + 1));
			}
			System.out.println();
		}
	}
}
